Kompresja danych (1)

Od prawie początku istnienia komputerów osobistych zaistniała potrzeba zmniejszania objętości danych. Z początku stosowanie kompresji było powodowane małą ilością megabajtów na nośnikach danych - jeszcze 10 lat temu standardowe 200 MB to było tyle co dziś standardowe 60 GB. Jednakże pomimo postępu w dziedzinie nośników danych kompresja jest nadal stosowana powszechnie z dwóch powodów - po pierwsze - Internet dla przeciętnego użytkownika to transfer od kilku do kilkunastu kb/s a przesłanie 1 MB zajmuje kilkanaście minut, po drugie - kompresja wprowadza ład skupiając dużą ilość plików w jednym.
Kompresją danych nazywamy tylko te zmiany zmniejszające objętość danych zachodzące na ich cyfrowej postaci, czyli wykluczamy tutaj np. wielowarstwowość płyt DVD czy też wielomodowość światłowodów, bowiem te metody upchania i przyspieszenia przesyłu manipulują na fizycznych obiektach takich jak płyta, czy ilość wiązek lasera i jego kolorów w światłowodzie.

Na czym polega kompresja danych? Istota jej jest dosyć prosta. Dane cyfrowe składają się z jedynek i zer zapisanych po 8 w szeregu tworząc bajt. Liczbie 2 odpowiada 01, a nie 01000000 jak by to powinno mieć miejsce. Im większa liczba, tym więcej pozycji jej zapisanie zajmuje, liczby powyżej 255 potrzebują już dodatkowego bajta. Wynika z tego, że zapisując cztery dwójki:
2222
zajmą one tyle co dwieście pięćdziesiąt pięć:
255
Wysuwa się z tego rzecz następująca - najczęściej powtarzający się znak zastąpimy jedynką, która zajmuje najmniej miejsca, a resztę hierarchicznie według częstości ich występowania. W tekście polskim najczęściej występuje "a" - 11%, tuż za jest "e" - 9% itd. a w angielskim pierwsze jest "e". Kompresja wydziela te znaki analizując kawałki danych. Dzięki temu da się zaoszczędzić nawet połowę miejsca.
W takiej kompresji na początku łańcucha lub pliku zapisywana jest tabela opisująca jak znaki były zmieniane. Kompresja taka nazwana jest kompresją Huffmana.

Inna metoda kompresju - Lampel-Ziv-Welch (LZW) analizuje dane znak po znaku i zapisuje każdą kombinację (frazę) przypisując jej numer i zapisując do specjalnej tabeli. W przypadku powtórzenia się kombinacji, nie jest ona znowu zapisywana do tabeli. Jest to bardzo skomplikowana metoda i co najważniejsze przy zróżnicowanych danych nie sprawdza się, jednak np. przy grafice jest doskonała.

Do grafiki także szczególnie nadaje się Run-Leght Encoding (RLE). Jeśli znak powtórzy się więcej niż trzy razy, to jest zapisywany tylko ten znak i liczba powtórzeń. Przedstawiam poniżej schemat - przed znakiem ^ jest liczba powtórzeń. Łańcuch danych do przetwarzania:
DDDDDDBBNNNNKKKKKOOO
po skompresowaniu:
6^DBB4^N5^KOOO
Jak widać zaoszczędziliśmy około 25% miejsca. Oczywiście w rzeczywistości nie wygląda to tak, wszystko odbywa się na bitach i w rezultacie widnieją tu całkowicie inne znaki. Poniżej znajdują się funkcje do kompresji i dekompresji RLE. Odpowiednie ich zastosowanie, poprzez równoległe przetwarzanie porcjowe pozwala efektywnie i szybko "pakować" grafikę.

Public Sub RLECompress(txtDataIn As String, txtDataOut As String)
    Dim intCharCount As Integer
    Dim intNewChar As Integer
    Dim intLastChar As Integer
    Dim intCharLoop As Integer
    Dim lonCharPtr As Long
    Dim lonCharStrLen As Long
    Dim strCompressed As String
    Dim bytMgrChar As Byte
    
    intCharCount = -1
    lonCharStrLen = Len(txtDataIn)
    
    For lonCharPtr = 1 To (lonCharStrLen + 1)
    If lonCharPtr < lonCharStrLen + 1 Then
        intNewChar = Asc(Mid(txtDataIn, lonCharPtr, 1))
    Else
        intNewChar = -1
    End If
    
    intCharCount = intCharCount + 1
    If lonCharPtr > 1 Then
        If intNewChar = intLastChar Then
            If intCharCount = 128 Then
                bytMgrChar = 128
                bytMgrChar = bytMgrChar Or 127
                strCompressed = strCompressed & Chr(bytMgrChar) & Chr(intLastChar)
                intCharCount = 0
            End If
        Else
            If intCharCount > 2 Then
                bytMgrChar = 128
                bytMgrChar = bytMgrChar Or (intCharCount - 1)
                strCompressed = strCompressed & Chr(bytMgrChar) & Chr(intLastChar)
            Else
                For intCharLoop = 1 To intCharCount
                    If bytLastChar > 127 Then
                        bytOutChar = 128
                        bytOutChar = bytOutChar Or (intCharCount - 1)
                        strCompressed = strCompressed & Chr(bytMgrChar) & Chr(intLastChar)
                    Else
                        strCompressed = strCompressed & Chr(intLastChar)
                    End If
                Next intCharLoop
            End If
            
            intCharCount = 0
        End If
    End If
    intLastChar = intNewChar
    Next lonCharPtr
    
    txtDataOut = strCompressed
End Sub

Public Sub RLEUncompress(txtDataIn As String, txtDataOut As String)
    Dim bytNewChar As Byte
    Dim intCharCount As Integer
    Dim lonCharPtr As Long
    Dim strUncompressed As String
    lonCharPtr = 0
    Do
        lonCharPtr = lonCharPtr + 1
        bytNewChar = Asc(Mid(txtDataIn, lonCharPtr, 1))
        If bytNewChar > 127 Then
            intCharCount = (bytNewChar And 127) + 1
            lonCharPtr = lonCharPtr + 1
            bytNewChar = Asc(Mid(txtDataIn, lonCharPtr, 1))
            strUncompressed = strUncompressed & String(intCharCount, bytNewChar)
        Else
            strUncompressed = strUncompressed & Chr(bytNewChar)
        End If
    Loop Until (lonCharPtr >= Len(txtDataIn))

    txtDataOut = strUncompressed
End Sub

Przy tworzeniu artykułu wykorzystano materiały z książki "Visual Basic 6 - księga eksperta" Rob'a Thay'era, wyd. Helion.

Marcin Porębski ( Doogie )
marcin.porebski@interia.pl